package genedit.aStar;

import genedit.model.graph.BreakPoint;

import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Collections;

/**
 * Algoritam za pretragu najkraćeg puta iscrtavanja veze tako da veza ne seče
 * druge grafičke elemente (ne računajući druge veze) ako ne mora.
 * 
 * @author Igić
 * @version 1.1 10/12/13
 */
public class Astar {
	/**
	 * Prostor stanja.
	 */
	private SearchMap map;
	/**
	 * Lista obrađenih čvorova.
	 */
	private ArrayList<Node> closedList;
	/**
	 * Lista čvorova koji treba da se obrade.
	 */
	private SortedNodeList openList;

	public Astar(SearchMap map) {
		this.map = map;

		closedList = new ArrayList<Node>();
		openList = new SortedNodeList();
	}

	/**
	 * Računa najkraću putanju između 2 konekcione tačke.
	 * 
	 * @param start
	 *            početna tačka od koje se kreće preračunavanje putanje
	 * @param goal
	 *            krajnja tačka do koje se izračunava putanja
	 * @return listu konekcionih tački enkapsuliranu u Path klasu
	 * @see Path
	 */
	public Path calcShortestPath(Point2D start, Point2D goal) {

		map.setStartLocation(start);
		map.setGoalLocation(goal);

		if (map.getNode(goal.getX(), goal.getY()).isObstacle) {
			return null;
		}

		map.getStartNode().setDistanceFromStart(0);
		closedList.clear();
		openList.clear();
		openList.add(map.getStartNode());

		while (openList.size() != 0) {

			Node current = openList.getFirst();

			if (current.getPosition().getX() == map.getGoalNode().getPosition().getX()
					&& current.getPosition().getY() == map.getGoalNode().getPosition().getY()) {
				return reconstructPath(current);
			}
			map.getGoalNode();
			openList.remove(current);
			closedList.add(current);

			for (Node neighbor : current.getNeighborList()) {
				boolean neighborIsBetter;

				if (closedList.contains(neighbor))
					continue;

				if (!neighbor.isObstacle) {

					double neighborDistanceFromStart = (current.getDistanceFromStart() + map
							.getDistanceBetween(current, neighbor));

					if (!openList.contains(neighbor)) {
						openList.add(neighbor);
						neighborIsBetter = true;
					} else if (neighborDistanceFromStart < current.getDistanceFromStart()) {
						neighborIsBetter = true;
					} else {
						neighborIsBetter = false;
					}

					if (neighborIsBetter) {
						neighbor.setPreviousNode(current);
						neighbor.setDistanceFromStart(neighborDistanceFromStart);
						neighbor.setHeuristicDistanceFromGoal(getEstimatedDistanceToGoal(neighbor
								.getPosition().getX(), neighbor.getPosition().getY(), map
								.getGoalNode().getPosition().getX(), map.getGoalNode()
								.getPosition().getY()));
					}
				}

			}

		}
		return null;
	}

	/**
	 * Metoda traži sve prelomne tačke definisane linijom dobijenom algoritmom
	 * A*.
	 * 
	 * @param node
	 *            - cilnji čvor od kojeg se rekurzivno dobijaju drugi
	 * @return listu prelomnih tačaka
	 */
	private Path reconstructPath(Node node) {
		Path path = new Path();
		while (!(node.getPreviousNode().getPreviousNode() == null)) {
			if ((node.getPreviousNode().getPreviousNode().getPosition().getX() == node
					.getPreviousNode().getPosition().getX()
					&& node.getPreviousNode().getPreviousNode().getPosition().getY() != node
							.getPreviousNode().getPosition().getY()
					&& node.getPosition().getX() != node.getPreviousNode().getPosition().getX() && node
					.getPosition().getY() == node.getPreviousNode().getPosition().getY())
					|| (node.getPreviousNode().getPreviousNode().getPosition().getX() != node
							.getPreviousNode().getPosition().getX()
							&& node.getPreviousNode().getPreviousNode().getPosition().getY() == node
									.getPreviousNode().getPosition().getY()
							&& node.getPosition().getX() == node.getPreviousNode().getPosition()
									.getX() && node.getPosition().getY() != node.getPreviousNode()
							.getPosition().getY()))
				if (!(node.getPosition().getX() == map.getGoalNode().getPosition().getX() && node
						.getPosition().getY() == map.getGoalNode().getPosition().getY()))
					path.prependBreakPoint(new BreakPoint(new Point2D.Double((int) node
							.getPreviousNode().getPosition().getX(), (int) node.getPreviousNode()
							.getPosition().getY())));
			node = node.getPreviousNode();
		}
		return path;
	}

	/**
	 * Metoda računa euklidsko rastojanje od starta do cilja.
	 * 
	 * @param startX
	 *            X koordinata početka
	 * @param startY
	 *            Y koordinata početka
	 * @param goalX
	 *            X koordinata cilja
	 * @param goalY
	 *            Y koordinata cilja
	 * @return rastojanje te dve tačke
	 */
	public double getEstimatedDistanceToGoal(double startX, double startY, double goalX,
			double goalY) {
		double dx = goalX - startX;
		double dy = goalY - startY;

		double result = (dx * dx) + (dy * dy);

		return result;
	}

	/**
	 * Služi za sortiranje elemenata liste.
	 */
	private class SortedNodeList {

		private ArrayList<Node> list = new ArrayList<Node>();

		public Node getFirst() {
			return list.get(0);
		}

		public void clear() {
			list.clear();
		}

		public void add(Node node) {
			list.add(node);
			Collections.sort(list);
		}

		public void remove(Node n) {
			list.remove(n);
		}

		public int size() {
			return list.size();
		}

		public boolean contains(Node n) {
			return list.contains(n);
		}
	}
}
